//用最少数量的简引爆气球
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        //端点相同的区间也是重叠区间，重叠区间只需使用一根箭
        int n = points.size();
        int ret = 0;
        sort(points.begin(),points.end());
        int left = points[0][0] , right = points[0][1];
        for(size_t i = 1 ; i < n ; ++i)
        {
            int a = points[i][0] , b = points[i][1];
            if(a <= right)
            {
                right = min(right , b);
            }
            else 
            {
                ret++;
                left = points[i][0] , right = points[i][1];
            }
        }
        if(points[n-1][0] <= right) ret++;
        return ret;
    }
};

//整数替换
class Solution {
public:
    int integerReplacement(size_t n) {
        int ret = 0;
        while(n != 1)
        {
            if(n % 2 == 0)
            {
                n /= 2;
            }
            else 
            {
                if(n == 3)
                {
                    n--;
                }
                else if((n >> 1) & 1)
                {
                    n++;
                }
                else 
                {
                    n--;
                }
            }
            ret++;

        }
        return ret;
    }
};

//俄罗斯套娃信封问题
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[](vector<int> & v1 , vector<int>& v2){
            if(v1[0] == v2[0]) return v1[1] > v2[1];
            else return v1[0] < v2[0];
        });
        //找出最长递增子序列
        vector<int> v;
        v.push_back(envelopes[0][1]);
        for(size_t i = 1 ; i < envelopes.size() ; ++i)
        {
            //二分
            //[<=target,>target]
            int b = envelopes[i][1];
            if(b > v.back())
            {
                v.push_back(b);
                continue;
            }
            int left = 0 , right = v.size()-1;
            while(left < right)
            {
                int mid = left + (right - left)/2;
                if(v[mid] < b) left = mid+1;
                else right = mid;
            }
            v[left] = envelopes[i][1];
        }

        return v.size();
    }
};

//可被三整除的最大和
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int INF = 0x3f3f3f3f;
        int sum = 0 , x1 = INF , x2 = INF , y1 = INF , y2 = INF;
        for(auto& x : nums)
        {
            sum += x;
            if(x % 3 == 1)
            {
                if(x < x1)
                {
                    x2 = x1;
                    x1 = x;
                }
                else if(x < x2)
                {
                    x2 = x;
                }
            }
            else if(x % 3 == 2)
            {
                if(x < y1)
                {
                    y2 = y1;
                    y1 = x;
                }
                else if(x < y2)
                {
                    y2 = x;
                }
            }
        }
        if(sum % 3 == 2)
        {
            //有一个 %3 == 2的数或者有两个%3 == 1的数
            sum -= min(x1+x2,y1);
        }
        else if(sum % 3 == 1)
        {
            //有两个 %3 == 2的数或者有一个%3 == 1的数
            sum -= min(y1+y2,x1);
        }
        return sum;
    }
};

//距离相等的条形码
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int count[10001] = {0};
        int maxCount = 0;
        int maxVal = 0;
        unordered_set<int> index;
        for(auto& x : barcodes)
        {
            count[x]++;
            index.insert(x);
            if(count[x] > maxCount)
            {
                maxCount = count[x];
                maxVal = x;
            }
        }
        index.erase(maxVal);
        vector<int> ret(barcodes.size());
        //先放最多的数
        for(size_t i = 0 ; i < barcodes.size() ; i+=2)
        {
            count[maxVal]--;
            ret[i] = maxVal;
            if(index.begin() != index.end() && count[maxVal] == 0)
            {
                maxVal = *(index.begin());
                index.erase(maxVal);
            }
        }
        for(size_t i = 1 ; i < barcodes.size() ; i+=2)
        {

            count[maxVal]--;
            ret[i] = maxVal;
            if(index.begin() != index.end() && count[maxVal] <= 0)
            {
                maxVal = *(index.begin());
                index.erase(maxVal);
            }
        }
        return ret;
    }
};

//重构字符串
class Solution {
public:
    string reorganizeString(string s) {
        int count[26] = {0};
        int maxVal = 'a';
        int maxCount = 0;
        unordered_set<char> index;
        for(auto &ch : s)
        {
            count[ch-'a']++;
            index.insert(ch);
            if(count[ch-'a'] > maxCount)
            {
                maxCount = count[ch-'a'];
                maxVal = ch;
            }
        }
        if(maxCount > (s.size()+1)/2) 
        {
            return "";
        }
        index.erase(maxVal);
        char buffer[512] = "";
        for(size_t i = 0 ; i < s.size() ; i+=2)
        {
            count[maxVal-'a']--;
            buffer[i] = maxVal;
            if(index.begin() != index.end() && count[maxVal-'a'] == 0)
            {
                maxVal = *(index.begin());
                index.erase(maxVal);
            }
        }
        for(size_t i = 1 ; i < s.size() ; i+=2)
        {
            count[maxVal-'a']--;
            buffer[i] = maxVal;
            if(index.begin() != index.end() && count[maxVal-'a'] == 0)
            {
                maxVal = *(index.begin());
                index.erase(maxVal);
            }
        }
        return buffer;
    }
};